package offer.day8;

import java.util.Arrays;

public class No11_quickSort {
    /*
     * 快速排序：
     * 算法思想：基于分治的思想，是冒泡排序的改进型。
     * 首先在数组中找到一个基准点（基准点的选择可能会影响快速排序的效率，在补充处）
     * 然后分别从数组的两端扫描数组，设两个指标（lo指向起始位置，hi指向末尾），
     * 首先从后半部分开始，若果发现有比基准点小的，就交换lo和hi的值，
     * 然后再从前半段开始扫描，发现有比基准点大的，就交换lo和hi的值，
     * 如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置
     * 一次排序就完成了
     * 接下来采用递归的方式分别对前半部分和后半部分排序，当前半部分有序、后半段有序，整个数组就自然有序列
     * 快速排序的时间复杂度是O(NlogN)
     *
     * 【补充】：基准点的选取
     * https://www.cnblogs.com/y3w3l/p/6444837.html
     * https://blog.csdn.net/liuyi1207164339/article/details/50827608
     *
     *
     * */

    public static void main(String[] args) {
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

    }

    public static void quickSort(int[] arr,int low,int high){
        if(low>high) return;
        int i=low;
        int j=high;
        //设置基准位
        int temp=arr[low];

        while(i<j){
            while(temp<=arr[j] && i<j){
                j--;
            }
            while(temp>=arr[i] && i<j){
                i++;
            }
            if(i<j){
                int t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
        arr[low]=arr[i];
        arr[i]=temp;
        quickSort(arr,low,j-1);
        quickSort(arr,j+1,high);
    }
}
